package com.java.comprehensive.other.sort;

import java.util.Arrays;

/**
 * @Author: Dgg
 * @Date: 2021/12/29 21:53
 */
public class HeapSort {

	public static void main(String[] args) {
		int[] array = {3, 2, 1, 5, 6, 4};
		buildHeap(array, array.length);
		System.out.println(Arrays.toString(array));
	}

	public static void heapify(int[] tree, int n, int i) {

		if (i >= n) {
			return;
		}
		int c1 = 2 * i + 1;
		int c2 = 2 * i + 2;
		int max = i;
		if (c1 < n && tree[c1] > tree[max]) {
			max = c1;
		}
		if (c2 < n && tree[c2] > tree[max]) {
			max = c2;
		}
		if (max != i) {
			swap(tree, max, i);
			heapify(tree, n, max);
		}

	}

	private static void swap(int[] tree, int i, int j) {
		int temp = tree[i];
		tree[i] = tree[j];
		tree[j] = temp;
	}

	public static void buildHeap(int[] tree, int n) {
		int lastNode = n - 1;
		int parent = (lastNode - 1) / 2;
		for (int i = parent; i >= 0; i--) {
			heapify(tree, n, i);
		}
	}

	public static void heapSort(int[] tree, int n) {
		buildHeap(tree, n);
		for (int i = n - 1; i >= 0; i--) {
			swap(tree, i, 0);
			heapify(tree, i, 0);
		}
	}
}
